package zuo.algo.c05;

import zuo.algo.data.LinkedNode;
import zuo.algo.util.LinkedUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * 01:45-复制含有随机指针的链表
 */
public class CopyRoundList {

    public static LinkedNode copy1(LinkedNode head) {
        if (head == null) {
            return null;
        }
        Map<LinkedNode, LinkedNode> map = new HashMap<>();
        LinkedNode node = head;
        while (node != null) {
            map.put(node, new LinkedNode(node.val));
            node = node.next;
        }
        LinkedNode headCopy = map.get(head);
        node = head;
        while (node != null) {
            LinkedNode nodeCopy = map.get(node);
            nodeCopy.next = node.next != null ? map.get(node.next) : null;
            nodeCopy.prev = node.prev != null ? map.get(node.prev) : null;
            node = node.next;
        }
        return headCopy;
    }

    public static LinkedNode copy2(LinkedNode head) {
        if (head == null) {
            return null;
        }
        LinkedNode node = head;
        while (node != null) {
            LinkedNode next = node.next;
            node.next = new LinkedNode(node.val);
            node.next.next = next;
            node = next;
        }
        node = head;
        while (node != null) {
            LinkedNode nodeCopy = node.next;
            nodeCopy.prev = node.prev;
            node = nodeCopy.next;
        }
        LinkedNode headCopy = head.next;
        LinkedNode nodeCopy = headCopy;
        node = headCopy.next;
        while (node != null) {
            nodeCopy.next = node.next;
            nodeCopy = nodeCopy.next;
            node = nodeCopy.next;
        }
        return headCopy;
    }

    public static void main(String[] args) {
        LinkedNode head = LinkedUtils.constructLinkedList(new int[]{1, 2, 3, 4});
        head.prev = head.next.next;
        head.next.prev = head;
        head.next.next.prev = head;
        head.next.next.next.prev = head;
        LinkedNode head1 = copy1(head);
        LinkedNode head2 = copy2(head);
        System.out.println();
    }
}
